﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Caca.MineSweeper.AI
{
    public class Analyst
    {
        MarkEventHandler Mark;
        UnCoverEventHandler Uncover;

        HashSet<Condition> ResolvedConditions;
        Stack<Condition> PendingConditions;
        int GameWidth, GameHeight;

        public Analyst(MarkEventHandler mark, UnCoverEventHandler uncover, Game game)
        {
            this.GameHeight = game.FieldHeight;
            this.GameWidth = game.FieldWidth;
            this.Mark = mark;
            this.Uncover = uncover;

            this.ResolvedConditions = new HashSet<Condition>();
            this.PendingConditions = new Stack<Condition>();

            var initCondition = ConditionFactory.Build(BuildInitFields(game), game.TotalMines);
            this.Pending(initCondition);
        }

        private static HashSet<Location> BuildInitFields(Game game)
        {
            HashSet<Location> fields = new HashSet<Location>();

            for (int y = 0; y < game.FieldHeight; y++)
                for (int x = 0; x < game.FieldWidth; x++)
                {
                    fields.Add(new Location() { X = x, Y = y });
                }

            return fields;
        }

        delegate void Move();

        public void NextMove()
        {
            // 分析条件
            ResolveConditions();

            Move m = CalculateMove();
            m();
        }

        public void Pending(int x, int y, Plot p)
        {
            var c = ConditionFactory.Build(x, y, p);

            Pending(c);
        }

        internal void Pending(Condition c)
        {
            PendingConditions.Push(c);
        }

        #region Analysis

        private Move CalculateMove()
        {
            Move move = null;

            // 计算出下一步动作

            // 标记已经确认是地雷的位置 和
            // 打开已经确认不是地雷的位置

            move = 打开或标记已确认的位置();
            if (move != null)
                return move;

            // 找出最不可能是地雷的条件分组
            var g = from rc in ResolvedConditions
                    group rc by rc.AveragePossibility into ap
                    where ap.Key > 0
                    orderby ap.Key ascending
                    select ap;

            //在分组中寻找打开时所获得信息最有利于扫雷游戏的格子
            var field = (from c in g.First()
                         from f in c.Fields
                         orderby 距离雷盘中心点的距离(f) ascending
                         select f).First();

            return BuildUncoverMove(field);
        }

        private double 距离雷盘中心点的距离(Location f)
        {
            double x = f.X - GameWidth / 2;
            double y = f.Y - GameHeight / 2;

            return Math.Sqrt(x * x + y * y);
        }

        private Move 打开或标记已确认的位置()
        {
            Move move = null;
            var sure = ResolvedConditions.OfType<SingleField>();

            if (sure.Count() > 0)
            {
                var c = sure.First();
                if (c.IsMine)
                {
                    move = BuildMarkMove(c.Field);
                }
                else
                {
                    move = BuildUncoverMove(c.Field);
                }
            }
            return move;
        }
        private Move BuildMarkMove(Location f)
        {
            return new Analyst.Move(() =>
            {
                Mark(f.X, f.Y);
            });
        }
        private Move BuildUncoverMove(Location f)
        {
            return new Analyst.Move(() =>
            {
                Uncover(f.X, f.Y);
            });
        }

        /// <summary>
        /// 使用各种方法分析新条件和已有条件
        /// </summary>
        private void ResolveConditions()
        {
            while (PendingConditions.Count > 0)
            {
                while (PendingConditions.Count > 0)
                {
                    var c = PendingConditions.Pop();

                    if (c is OpenedField)
                        处理OpenedField(c as OpenedField);

                    // 在 ResolvedConditions 内部的Condition是不应存在包含关系的
                    // 所以是处理 PendingConditions 与 ResolvedConditions 中Condition的包含关系
                    var shouldAbandonC = 处理条件中的包含关系(c);

                    if (!shouldAbandonC)
                        ResolvedConditions.Add(c);
                }

                找出已确认是或者不是地雷的单个格子();

                // ResolvedConditions 内的Condition的Fields可能存在交集, 检查这些交集有可能得出新的可确认的格子
                处理条件中的交集关系();
            }
        }

        private void 处理OpenedField(OpenedField openedField)
        {
            IEnumerable<Location> surrounds = openedField.Field.GetSurrounds();
            surrounds = from l in surrounds
                        where l.X > 0 && l.X < GameWidth && l.Y > 0 && l.Y < GameHeight
                        select l;
            var c = ConditionFactory.Build(surrounds, openedField.SurroundMines);
            Pending(c);
        }

        /// <summary>
        /// 表示若干格子里, 最多可能有多少个地雷, 最少会有多少个地雷
        /// </summary>
        class Prediction
        {
            internal IEnumerable<Location> Fields;
            /// <summary>
            /// 最多可以存在的地雷数
            /// </summary>
            internal int MaxMines;
            /// <summary>
            /// 最少必须存在的地雷数
            /// </summary>
            internal int MinMines;
        }

        /// <summary>
        /// 分析解析后的数据, 看能不能获得新信息或者推断
        /// </summary>
        private void 处理条件中的交集关系()
        {
            for (int i = 0; i < ResolvedConditions.Count; i++)
                for (int j = i + 1; j < ResolvedConditions.Count; j++)
                {
                    var c1 = ResolvedConditions.ElementAt(i);
                    var c2 = ResolvedConditions.ElementAt(j);
                    var intersection = c1.Fields.Intersect(c2.Fields);

                    if (intersection.Count() == 0)
                        continue;

                    // 交集在两个不同的条件中, 最多地雷数和最少地雷数可能是不一样的
                    var intersectionInC1 = BuildPrediction(intersection, c1);
                    var intersectionInC2 = BuildPrediction(intersection, c2);

                    // 合并两个推测, 取其中最严格的, 即最大的MinMines 和 最小的MaxMines
                    var intersectionPrediction = new Prediction()
                    {
                        Fields = intersection,
                        MaxMines = intersectionInC1.MaxMines < intersectionInC2.MaxMines ? intersectionInC1.MaxMines : intersectionInC2.MaxMines,
                        MinMines = intersectionInC1.MinMines > intersectionInC2.MinMines ? intersectionInC1.MinMines : intersectionInC2.MinMines
                    };

                    // 如果合并后的推论, 并不能确定有多少个地雷, 那该结论并没有用
                    if (intersectionPrediction.MaxMines != intersectionPrediction.MinMines)
                        continue;

                    var newCondition = ConditionFactory.Build(intersectionPrediction.Fields, intersectionPrediction.MaxMines);
                    Pending(newCondition);
                }
        }

        /// <summary>
        /// 生成在指定条件中, 特定格子内的地雷数推测
        /// </summary>
        /// <param name="fields">所推测的格子</param>
        /// <param name="c">格子所处的条件</param>
        /// <returns></returns>
        private static Prediction BuildPrediction(IEnumerable<Location> fields, Condition c)
        {
            int totalMines = c.Mines;
            int totalFieldsCount = c.Fields.Count();
            var calculatingFieldsCount = fields.Count();
            var otherFieldsCount = totalFieldsCount - calculatingFieldsCount;

            var result = new Prediction
            {
                Fields = fields,
                MaxMines = calculatingFieldsCount > totalMines ? totalMines : calculatingFieldsCount,
                MinMines = otherFieldsCount > totalMines ? 0 : totalMines - otherFieldsCount
            };
            return result;
        }

        private void 找出已确认是或者不是地雷的单个格子()
        {
            //找出已经推断出一定是或者一定不是地雷的格子, 再分拆成单独的条件
            var sure = from rc in ResolvedConditions.OfType<MinesInFields>()
                       where rc.Mines == 0 || rc.Mines == rc.Fields.Count
                       select rc;

            foreach (var rc in sure)
            {
                foreach (var field in rc.Fields)
                {
                    var c = ConditionFactory.Build(field, rc.Mines != 0);
                    Pending(c);
                }
            }
        }

        /// <summary>
        /// 代表 HashSet&lt;Field&gt; 之间的三种关系
        /// </summary>
        enum FieldsRelation
        {
            Subset, Superset, Equal
        }

        /// <summary>
        /// 处理新条件与旧条件之间, 所有的包含或者被包含关系
        /// 并将得出的新条件加入PendingConditions, 无用的旧条件
        /// </summary>
        /// <param name="c"></param>
        private bool 处理条件中的包含关系(Condition c)
        {

            // 包含是指一个Condition中的Fields是另一个Condition的Fields的真超集
            // 即 newCondition.Fields.IsProperSupersetOf (oldCondition.Fields) 为 true

            // 本方法分析建立在一个推定上: 
            // ResolvedConditions中的Condition互相之间不存在包含或者被包含的关系, 这样的关系必定在上次分析中被处理完成

            // 所以被检查的Condition 与 ResolvedConditions 中Condition的关系只存以下情况
            // 1: 新Conditino包含了 ResolvedConditions 中一个或多个Condition
            // 2: 新Condition被 ResolvedConditions 中一个或多个Condition 所包含
            // 3: 新Condition 与 ResolvedConditions 中的一个 Condition 相等

            FieldsRelation? fr = CalcFieldsRelation(c);
            bool shouldAbandonC = false;

            if (fr.HasValue)
            {
                switch (fr)
                {
                    case FieldsRelation.Subset:

                        // 如果被检查条件是旧条件的子集
                        // 将计算出来的新条件加入Pending, 将包含了被检查条件的旧条件删除
                        // 最后将被检查条件加入ResolvedConditions

                        var subsetOf = from rc in ResolvedConditions
                                       where c.Fields.IsProperSubsetOf(rc.Fields)
                                       select rc;

                        foreach (var rc in subsetOf.ToList())
                        {
                            var otherFields = rc.Fields.Except(c.Fields);
                            var mines = rc.Mines - c.Mines;

                            Condition newCondition = ConditionFactory.Build(otherFields, mines);
                            Pending(newCondition);

                            ResolvedConditions.Remove(rc);
                        }

                        shouldAbandonC = false;
                        break;

                    case FieldsRelation.Superset:

                        // 如果被检查条件是旧条件的超集
                        // 将计算出来的新条件加入Pending
                        // 最后放弃被检查条件, 不加入ResolvedConditions

                        var supersetOf = from rc in ResolvedConditions
                                         where c.Fields.IsProperSupersetOf(rc.Fields)
                                         select rc;

                        foreach (var rc in supersetOf.ToList())
                        {
                            var otherFields = c.Fields.Except(rc.Fields);
                            var mines = c.Mines - rc.Mines;

                            Condition newCondition = ConditionFactory.Build(otherFields, mines);
                            Pending(newCondition);
                        }
                        shouldAbandonC = true;
                        break;

                    case FieldsRelation.Equal:

                        // 如果被检查条件与旧条件的格子相等
                        // 则用条件更严格的(地雷数更少)的条件替换原条件

                        var equal = ResolvedConditions.First(rc => rc.Fields.SetEquals(c.Fields));
                        if (equal.Mines > c.Mines)
                        {
                            ResolvedConditions.Remove(equal);
                            shouldAbandonC = false;
                        }

                        break;

                }
            }

            return shouldAbandonC;
        }

        private FieldsRelation? CalcFieldsRelation(Condition c)
        {
            FieldsRelation? fr = null;

            if (ResolvedConditions.Any(rc => c.Fields.IsProperSubsetOf(rc.Fields)))
            {
                fr = FieldsRelation.Subset;
            }
            else if (ResolvedConditions.Any(rc => c.Fields.IsProperSupersetOf(rc.Fields)))
            {
                fr = FieldsRelation.Superset;
            }
            else if (ResolvedConditions.Any(rc => c.Fields.SetEquals(rc.Fields)))
            {
                fr = FieldsRelation.Equal;
            }

            return fr;
        }

        #endregion
    }
}
